TIL

190419_TIL(버블정렬(Bubble sort)정리)

컴퓨터공학기초

4월 19일(금)

  • 오늘은 기본정렬 알고리즘 중 버블정렬에 대하여 배웠다. 이 포스트에서는 나름대로 이해한 내용을 정리해보려 한다.
  • 버블정렬을 이용하여 오름차순으로 정렬하기 위한 방법이다.
  • 먼저, 버블정렬의 매커니즘을 알아보자.

  • 다음과 같은 리스트가 있다고 가정하자

    1
    li=[6, 2, 1, 4]

  • 먼저, 버블정렬은 0번 인덱스의 들어있는 값과 1번 인덱스의 들어 있는 값을 비교한다. 즉, 위 리스트의 6과 2를 비교한다.

  • 만약, 0번 인덱스의 값이 1번 인덱스의 값보다 더 크다면 두 값을 교환한다. 그렇지 않으면 교환하지 않는다. 위의 리스트의 0번 인덱스 값인 6이 1번 인덱스 값인 2보다 크기 때문에 두 값을 교환한다.

  • 두 값을 교환한 리스트는 다음과 같다.

    1
    li=[2, 6, 1, 4]

  • 순차적으로 1번 인덱스와 2번 인덱스 , 2번 인덱스와 3번 인덱스를 비교한다.

  • 위와 같은 방법으로 값을 교환한다.

  • 위와 같은 방법으로 전체 리스트를 한번씩 비교 하고 난 후의 리스트는 다음과 같다.

    1
    li=[2, 1, 4, 6]

  • 큰 값을 뒤 순서로 보내는 교환을 진행하였기 때문에 전체 리스트에서 가장 큰 값이 가장 뒤에 정렬되어 있는 모습을 볼 수 있다.

  • 따라서, 다음 비교에서는 이미 정렬된 가장 큰 값은 비교할 필요가 없다.

  • 위 방법으로 0번과 1번 , 1번과 2번을 비교하고 교환한 리스트는 다음과 같다.

    1
    li=[1, 2, 4, 6]

  • 두 번째로 큰 값이 오름차순으로 정렬된 것은 물론이거니와 운이 좋게도 모든 정렬이 끝난 결과을 얻었다.

  • 하지만, 컴퓨터는 정렬이 끝났는지 알 수 있는 방법이 없기 때문에 마지막으로 0번 인덱스와 1번 인덱스의 값을 비교한다. 비로소 컴퓨터도 정렬을 끝내었다.
  • 다음으로, 버블정렬을 구현하기 위한 코드를 생성해보자.

  • python 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def bubble_sort(li):
        n=len(li) #리스트의 길이 , n=4
        for i in range(n-1): # range(3): 0부터 ()안 숫자 미만의 숫자를 포함하는 객체 생성. 0, 1 ,2의 값을 가짐.
            for j in range(n-1-i):
                print(j)
                if li[j] > li[j+1]: # 인덱스 값을 비교
                    li[j], li[j+1] = li[j+1], li[j]   # 인덱스의 값을 교환

    if __name__=="__main__":
        li=[6, 2, 1, 4]
        bubble_sort(li)
        print(li)

  • 코드 분석

    1. 바깥쪽 for문을 이용하여 전체 인덱스 비교를 n-1회 한다.(왜 n-1회 인지는 위 매커니즘 과정을 직접 따라가보면 알 수 있다.)
    2. 바깥쪽 for문을 한번 돌 때마다(i가 1씩 증가) 안쪽 for문의 최대 교환 횟수가 1씩 감소하기 때문에 -i를 해준다.
    3. i=0 일 때 j=0, j=1, j=2 i=1 일 때 j=0, j=1 i=2 일 때 j=0의 순서로 바깥쪽 for문과 안쪽 for문이 작동한다.
    4. 모든 for문이 완료되면 오름차순으로 잘 정렬된 리스트를 볼 수 있다.

  • 관련사이트

  • 관련사이트에서 위 코드를 복사하여 붙여넣고 Visualize Execution 버튼을 클릭하여 넘어간 페이지에서 Back 버튼과 Foward 버튼을 활용하면 버블정렬의 메커니즘을 좀 더 확실히 파악하는데 도움이 된다.

Share